1. Field of the Invention
The present invention relates to a method and apparatus for pattern data processing which allows a computer to create, modify, and synthesize a pattern. More specifically, this invention relates to a method and apparatus for pattern processing which is suitable for modifying patterns maintaining the original features and characteristics of the patterns.
2. Description of the Related Art
A technology for inputting pattern data into a computer and generating patterns in a computer is disclosed in the reference (A) of the following reference list. Approximate calculation methods for internal processing of patterns are described in the literatures (B) and (C). A method of making a principal description of pattern data in a computer and generating a geometric model of the pattern and displaying the patterns, is disclosed in the reference (D). The reference (F) describes a method of holding temporary data during pattern processing as a geometric constraint and a method of parametric modification of a pattern using geometric constraint relations, and furthermore a pattern correction method based on geometric inference. The reference (E) discloses a method of describing meanings of pattern data by attribute data and a method of performing automatic conversion of geometric models into another data description form, such as a finite-element model, using a means of interpreting the attribute data.
(A) Toshio Ochi, "Graphic Image Processing System GIPS--I", Mechanical Design, Vol. 16(7), pp. 29-37(1972) PA0 (B) Fujio Yamaguchi, "Pattern Processing Engineering--I, II, III", The Nikkan Kogyo Shinbun, LTD. PA0 (C) Hiroaki Chiyokura, "Solid Modeling", Kogyo Chosakai Publishing Co., LTD. PA0 (D) Japanese Patent Application No. 61-4933, "Method of Graphic Layout Display" PA0 (E) Japanese Patent Application No. 1-318163, "Method and Apparatus for Automatic Division into Elements" PA0 (F) Yasumasa Kawashima, "An Automatic Shape Modification Using Surface Constraint in CSG", Journal of the Japan Society for Precision Engineering, Vol. 56(4), pp. 703-708(1990) PA0 (1) Significance description means; PA0 (2) Characteristic information input means; PA0 (3) Characteristic information extraction means; PA0 (4) Characteristic information describing means; and PA0 (5) A pattern processing means for referencing to characteristic information.
In conventional technologies described in the above references, only pattern data or attribute data needed for interpretation based on the knowledge engineering are retained and used. Therefore, it is impossible to keep the input general characteristics during editing processing or modification processing of the pattern. This problem is described further below in detail.
When pattern processing is carried out using a computer, calculations required for the processing are, in general, achieved by the numerical calculations. As a result, the pattern processing suffers calculation errors of a computer, numerical calculation errors, and approximating representation errors. For example, when a length of a curve between two points is calculated approximating a curve by a line or an arc, there occurs an approximating representation error between these two approximation methods. Because a computer deals with limited digits of numbers, the calculation errors depend on the precision of the calculation or the number of significant digits effective in calculation. That is, even if a length of an arc is calculated using an equation which analytically represents a circle, calculation errors of a computer bring about an error in the calculated length compared to the real length. Furthermore, if a length of an arc is determined by approximate numerical calculation based on the trapezoidal rule or Simpson's rule, the error appears due to the difference in a method of calculation, in addition to the error due to the approximate numerical calculation. Accordingly, in a current method of pattern processing, the errors described above always cause a problem.
When a pattern is created, in addition to the errors described above, another important consideration is what a user intends for his/her pattern creation. For example, the pattern may be required to deal with information of a sense which cannot be represented adequate by mathematics or science. That is, the sense to be dealt with is such as "smoothness" or "swelling feature of a surface" of patterns, which are based on a subjective sense. These senses represent what is called geometric definitions of a pattern, however a means of geometric representation of a sense is not established yet, thus it is difficult to create a pattern as a user requires.
When errors described above are combined with a problem of the intended purpose of the creation, various problems occur. For example, in the case of the processing to determine a point at which two lines intersect, numerical calculation can determine the point of intersection, but the calculation might be incorrect. A more concrete example is when an intersection point is to be determined between two lines A and B which can be considered to exist on the same plane within a small error, and the resultant intersection point is one of the following three types. The first type is a point in a three-dimensional space which is simply determined by numerical calculation. The second and the third types are a point on either line A or line B which is infinitely near the first type intersection point in a three-dimensional space. Which intersection point among these three is correct should be decided from the view point of the intended purpose of the creation. If, moreover, the point is to be created with complicated purpose, there might be other various intersection points rather than just these three mentioned types. As a result, there exists a problem that it is impossible to create a pattern as a user requires.
In current pattern processing systems or CAD systems, these errors or intended purposes of creation are interpreted and processed in a certain predetermined way and the user's intentions in his/her creation are neglected. For example, as for the three type intersection points described above, one of these is unequivocally selected during the pattern processing by systems or apparatus. Accordingly, there exists a problem that the created pattern is different from what the user intends. In order to solve a part of this problem, the method of geometric constraint, which describes the geometric states that each portion of a pattern has to satisfy, was described in the prior art reference (F).
Although the technology of geometric constraint can describe simple geometric states, it cannot fully conduct certain kinds of processing because the problem set forth above is not taken into account in this technology. Even if it is assumed that there are no errors attributable to the above-mentioned problem, there are still some geometric states which this technology cannot properly describe. Furthermore, in some cases, even the geometric state itself cannot be described. For example, in the case that the intersection point has been determined between an arc and a line, when the arc is moved, the method of geometric constraint allows the line to automatically follow the movement of the arc, maintaining the connection state of the intersection point. However, when this is done in the processing of a movement together with an enlargement or reduction of the pattern, which is called offset, the description of the state of the intersection point is sufficient, that is, means for changing the state of an intersection point is not defined well enough to describe the geometric states each portion of a pattern has to satisfy after the processing. A concrete example is when a pattern is enlarged and moved, the position of an intersection point shifts and it becomes difficult to describe the connection state. When a pattern is reduced and moved, an intersection point disappears and it becomes impossible to describe the connection state.
For example, when a pattern consisting of two lines 601 and 602 which are connected to each other at a right angle at a point 502 (X2, Y2, Z2) is offset in the direction denoted by the arrows shown in FIG. 6, the processing of offsetting changes pattern data from those described on the left side in the figure to those described on the right side. The resultant pattern based on the data after the processing consists of two separated lines which no longer have an intersection point. In order to keep the connection state as a geometric constraint in these cases, another procedure is required, such as re-calculation of the intersection point or extension of pattern elements. However, in order to carry out these procedures correctly, an intersection point or pattern elements must be defined. If these definitions are described by a vague expression such as a character string called an attribute, problems arise in that geometric definitions of patterns become vague or lengthy and it becomes necessary to carry out various kinds of interpretations.
As an example of the problem, when the state of the intersection point between the arc and the line described above is the first one among three types, that is, a three-dimensional intersection point, the state which can describe the pattern characteristics of this point is not clearly defined. On the other hand, when the second type intersection point exists on a line, it is possible to describe the situation that the point exists on the line, but on the other hand, it is difficult to describe the characteristics of the arc. In the case of the third type intersection point existing on an arc, there is also a similar problem. That is, just a simple description of geometric state--an intersection point--cannot represent geometric definitions sufficiently.
As described above, in conventional technologies, it is impossible to perform the modification of linked patterns, and it is also impossible to perform correct creation or conversion of patterns in editing or creation procedures just as a user wants to do. As a result, it is necessary to carry out a huge amount of operations for making correction, such as re-generation of pattern data or modification. In order to solve these problems, in addition to a simple description of geometric states, the change in state has to also be described to achieve the description of real dynamic pattern states.